//给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。
//
// 注意：此题 matrix 输入格式为一维 01 字符串数组。
//
//
//
// 示例 1：
//
//
//
//
//输入：matrix = ["10100","10111","11111","10010"]
//输出：6
//解释：最大矩形如上图所示。
//
//
// 示例 2：
//
//
//输入：matrix = []
//输出：0
//
//
// 示例 3：
//
//
//输入：matrix = ["0"]
//输出：0
//
//
// 示例 4：
//
//
//输入：matrix = ["1"]
//输出：1
//
//
// 示例 5：
//
//
//输入：matrix = ["00"]
//输出：0
//
//
//
//
// 提示：
//
//
// rows == matrix.length
// cols == matrix[0].length
// 0 <= row, cols <= 200
// matrix[i][j] 为 '0' 或 '1'
//
//
//
//
// 注意：本题与主站 85 题相同（输入参数格式不同）： https://leetcode-cn.com/problems/maximal-
//rectangle/
//
// Related Topics 栈 数组 动态规划 矩阵 单调栈 👍 83 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function maximalRectangle(matrix: string[]): number {

    /*
    ? 从矩阵中找出直方图，那么就能通过计算直方图中的最大矩形面积来计算矩阵中的最大矩形面积
    ? 将矩阵中上下相邻的值为1的格子看成直方图中的柱子
     */
    //? 这就相当于单调递增栈解最大面积了
    function largestRectangleArea(heights) {
        let stack = [-1];
        let maxArea = 0;
        for (let i = 0; i < heights.length; i++) {
            //? 当前柱子的高度小于位于栈顶的柱子的高度
            while (
                stack[stack.length - 1] != -1 &&
                heights[stack[stack.length - 1]] >= heights[i]
                ) {
                //? 以栈顶的柱子为高度计算面积
                let height = heights[stack.pop()];
                let width = i - stack[stack.length - 1] - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            //? 当前柱子的高度大于位于栈顶的柱子的高度  入栈
            stack.push(i);
        }
        //? 计算末尾
        while (stack[stack.length - 1] != -1) {
            let height = heights[stack.pop()];
            let width = heights.length - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        return maxArea;
    };
    /**
     * @param {string[]} matrix
     * @return {number}
     */
    if (matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    let heights = new Array(matrix[0].length).fill(0);
    let maxArea = 0;
    for (let row of matrix) {
        for (let i = 0; i < row.length; i++) {
            if (row[i] == "0") {
                heights[i] = 0;
            } else {
                heights[i]++;
            }
        }
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }
    return maxArea;


};
//leetcode submit region end(Prohibit modification and deletion)
